{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 21.1 Disjoint-set operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.1-1\n",
    "\n",
    "> Suppose that CONNECTED-COMPONENTS is run on the undirected graph $G = (V, E)$, where $V = \\{a, b, c, d, e, f, g, h, i, j, k\\}$ and the edges of $E$ are processed in the order $(d, i), (f, k), (g, i), (b, g), (a, h), (i, j), (d, k), (b, j), (d, f), (g, j), (a, e)$. List the vertices in each connected component after each iteration of lines 3–5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Edge processed | Collection of disjoint sets |\n",
    "|:--------------:|:---------------------------:|\n",
    "|  initial sets  | $\\{a\\}~~~\\{b\\}~~~\\{c\\}~~~\\{d\\}~~~\\{e\\}~~~\\{f\\}~~~\\{g\\}~~~\\{h\\}~~~\\{i\\}~~~\\{j\\}~~~\\{k\\}$ |\n",
    "| $(d, i)$ | $\\{a\\}~~~\\{b\\}~~~\\{c\\}~~~\\{d, i\\}~~~\\{e\\}~~~\\{f\\}~~~\\{g\\}~~~\\{h\\}~~~\\{j\\}~~~\\{k\\}$ |\n",
    "| $(f, k)$ | $\\{a\\}~~~\\{b\\}~~~\\{c\\}~~~\\{d, i\\}~~~\\{e\\}~~~\\{f, k\\}~~~\\{g\\}~~~\\{h\\}~~~\\{j\\}$ |\n",
    "| $(g, i)$ | $\\{a\\}~~~\\{b\\}~~~\\{c\\}~~~\\{d, i\\}~~~\\{e\\}~~~\\{f, k\\}~~~\\{g\\}~~~\\{h\\}~~~\\{j\\}$ |\n",
    "| $(b, g)$ | $\\{a\\}~~~\\{b, g\\}~~~\\{c\\}~~~\\{d, i\\}~~~\\{e\\}~~~\\{f, k\\}~~~\\{h\\}~~~\\{j\\}$ |\n",
    "| $(a, h)$ | $\\{a, h\\}~~~\\{b, g\\}~~~\\{c\\}~~~\\{d, i\\}~~~\\{e\\}~~~\\{f, k\\}~~~\\{j\\}$ |\n",
    "| $(i, j)$ | $\\{a, h\\}~~~\\{b, g\\}~~~\\{c\\}~~~\\{d, i, j\\}~~~\\{e\\}~~~\\{f, k\\}$ |\n",
    "| $(d, k)$ | $\\{a, h\\}~~~\\{b, g\\}~~~\\{c\\}~~~\\{d, f, i, j, k\\}~~~\\{e\\}$ |\n",
    "| $(b, j)$ | $\\{a, h\\}~~~\\{b, d, f, g, i, j, k\\}~~~\\{c\\}~~~\\{e\\}$ |\n",
    "| $(d, f)$ | $\\{a, h\\}~~~\\{b, d, f, g, i, j, k\\}~~~\\{c\\}~~~\\{e\\}$ |\n",
    "| $(g, j)$ | $\\{a, h\\}~~~\\{b, d, f, g, i, j, k\\}~~~\\{c\\}~~~\\{e\\}$ |\n",
    "| $(a, e)$ | $\\{a, e, h\\}~~~\\{b, d, f, g, i, j, k\\}~~~\\{c\\}$ |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.1-2\n",
    "\n",
    "> Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21.1-3\n",
    "\n",
    "> During the execution of CONNECTED-COMPONENTS on an undirected graph $G = (V, E)$ with $k$ connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of $|V|$, $|E|$, and $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FIND-SET: $2|E|$.\n",
    "\n",
    "UNION: Initially, there are $|V|$ components, and each UNION operation decreases the number of connected components by 1, thus UNION is called $|V| - k$ times."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
